package pen_exam.yongyou_2020_10_26;

import java.util.*;

public class Class02_DagBfsTraversal {

    public static  class Node{
        String node;
        ArrayList<Node> next;

        public Node(String node) {
            this.node = node;
            this.next = new ArrayList<>();
        }
    }
    public static   String dagBfsTraversal (String[] nodes, String startNode) {
        // write code here
        Node start = new Node(startNode);
        HashMap<String,Node> nodeMap = new HashMap<>();
        LinkedHashSet<String> haved = new LinkedHashSet<>();
        HashSet<Node> visited =  new HashSet<>();
        for (String node : nodes) {
            String[] n = node.replace(" ","").split("->");
            String from = n[0];
            String[] to = n[1].split(",");
            if(!haved.contains(from)){
                haved.add(from);
                Node fromNode = new Node(from);
                haved.add(from);
                nodeMap.put(from,fromNode);
            }
            Node fromNode = nodeMap.get(from);
            for(String  toNode : to){
                if(!haved.contains(toNode)){
                    haved.add(toNode);
                    Node toNodeNode = new Node(toNode);
                    nodeMap.put(toNode,toNodeNode);
                }
                fromNode.next.add(nodeMap.get(toNode));
            }
        }

        Queue<Node> queue = new LinkedList<>();
        queue.add(nodeMap.get(startNode));
        StringBuilder sb = new StringBuilder();
        while(!queue.isEmpty()){
            Node cur = queue.poll();
            haved.remove(cur.node);
            visited.add(cur);
            sb.append(cur.node + ",");
            for(Node next : cur.next){
                if(!visited.contains(next)){
                    queue.add(next);
                }
            }
        }
        if (!haved.isEmpty()){
          haved.forEach((x) ->{sb.append(x + ",");});
        }
        return sb.toString().substring(0,sb.length()-1);
    }

    public static void main(String[] args) {
        String[] nodes = {"A -> B","A -> C,D","C->E","E->F","D->G","G->E"};
        String start = "A";
        System.out.println(dagBfsTraversal(nodes,start));
    }
}
